/****************************************
* 2、编写一个算法，实现两个采用三元组表示的
* n阶稀疏矩阵的加法运算。
*****************************************/

#include<stdio.h>
#include<malloc.h>

typedef struct {int col,row,data;} triple;


void display_sparse_mat_table(const triple* m){
    printf("<SparseMatrix %dx%d with %d element%s>\n",m->row,m->col,m->data,m->data>1?"s":"");
    if(m->data)printf(" row| col|data\n");
    for(int i=1;i<=m->data;i++)
        printf("%4d|%4d|%4d\n",m[i].row,m[i].col,m[i].data);
}

// returns sparse matrix A+B 
triple* sparse_mat_add(const triple* A,const triple* B){
    if(A->col!=B->col || A->row != B->row)return NULL;
    triple* m = malloc(sizeof(triple)*((A->data)+(B->data)+1)); // monoploy programming
    m->data = 0; m->row = A->row; m->col=A->col;
    int i,j,k,idx_a,idx_b;
    i = j = k = 1;
    while(i<=A->data || j<=B->data){
        // position
        idx_a = A[i].row * A->row + A[i].col;
        idx_b = B[j].row * B->row + B[j].col;
        if(idx_a==idx_b){
            m[k].data = A[i].data+B[j].data;
            m[k].row = A[i].row; m[k].col = A[i].col;
            m->data++;i++;j++;k++;
        }
        else if(idx_a < idx_b){
            m[k].data = A[i].data;
            m[k].col = A[i].col; m[k].row = A[i].row;
            i++;k++;m->data++;
        }else{
            m[k].data = B[j].data;
            m[k].col = B[j].col; m[k].row = B[j].row;
            j++;k++;m->data++;
        }
    }
    return realloc(m,sizeof(triple)*(m->data+1));
}

int main(){
    int i,j,k;
    triple* mat_a,*mat_b;
    printf("Enter sparse matrix size, row,col,and mnumber of non-zero elements: ");
    scanf("%d%d%d",&i,&j,&k);
    mat_a = malloc(sizeof(triple)*(k+1));
    mat_a->row = i;
    mat_a->col = j;
    mat_a->data = k;
    printf("Enter mat elements: row,col,data \n");
    for(i=1;i<=mat_a->data;i++){
        printf("Element #%d> ",i);
        scanf("%d%d%d",&mat_a[i].row,&mat_a[i].col,&mat_a[i].data);
        fflush(stdin);
    }
    display_sparse_mat_table(mat_a);

    

    printf("Enter number of second mat non-zero elements: ");
    scanf("%d",&k);
    mat_b = malloc(sizeof(triple)*(k+1));
    mat_b->row = mat_a->row;
    mat_b->col = mat_a->col;
    mat_b->data = k;
    printf("Enter second mat elements: row,col,data \n");
    for(i=1;i<=mat_b->data;i++){
        printf("Element #%d> ",i);
        scanf("%d%d%d",&mat_b[i].row,&mat_b[i].col,&mat_b[i].data);
        fflush(stdin);
    }
    display_sparse_mat_table(mat_b);

    triple* sum = sparse_mat_add(mat_a,mat_b);

    display_sparse_mat_table(sum);

    free(sum); free(mat_a); free(mat_b);
    
    return 0;
}
